Prior digital systems, including digital computers, have used various algorithms for signed and unsigned binary multiplication. FIG. 1 illustrates a simple example of prior art binary multiplication. A binary multiplicand is multiplied by a binary multiplier. A series of shifted partial products are formed, given that the only possible values of the multiplier digits are zero and one. The shifted partial products are then added, resulting in a product. When an N-bit word is multiplied by an M-bit word in a digital system, the resulting product will be N+M bits in length. Thus, a four-bit multiplicand times a four-bit multiplier results in an eight-bit product, as shown in FIG. 1.
In simple binary multiplication, partial products are formed by using one-bit of the multiplier at a time, starting with the least significant bit of the multiplier. The simplest way to generate partial products is to use AND gates as bit-by-bit multipliers. Using this simple multiplication technique, an N-bit multiplier generates N partial products.
Prior approaches have used encoding techniques to reduce the number of partial products. Reducing the number of partial products reduces the number of additions that need to be performed. Reducing the number of additions in turn reduces the number of clock cycles necessary for binary multiplication. One prior approach uses a modified Booth's algorithm as an encoding technique to reduce the number of partial products by one-half.
In a modified version of Booth's algorithm, each multiplier is divided into substrings of three-bits, with adjacent groups sharing a common bit. In one prior approach, the common bit is a prior bit. An encoding table is used to set forth the multiplication operation to be used for each of the eight permutations of the three multiplier bits.
Booth's algorithm can be used with either unsigned or two's complement numbers. In past approaches, multipliers have been padded with one or more zeroes to the right if necessary to form complete groups of three-bits each. To work with unsigned numbers, the multipliers have also been padded with one or two zeroes to the left.
Once shifted partial products are formed, they must be added together. Several types of conventional adders exist. One conventional two-input adder is called a carry propagate adder ("CPA"). The carry propagate adder adds a sum vector to a carry vector to produce one final sum. A CPA is a type of full adder. A full adder has three inputs and two outputs.
Another type of adder is the carry-save adder ("CSA"). CSA full adders and CSA half adders exist. A half adder has only two inputs, and it produces a sum and carry output. Carry-save adders are useful when multiple additions are performed.
Carry-save adders save the carry propagation until all the additions are completed. In one past approach, a carry propagate adder is then used during a final clock cycle to complete the carry propagation for all the additions.
The multiplication of negative numbers has been handled by converting a number into its two's complement form. If a number is positive, the two's complement of that number is the number itself. If a number X is negative, the two's complement of X is 2exp(n)-.vertline.X.vertline., wherein n is the number of bits in a storage location and X is less than zero. If the absolute value of X is less than 2exp(n-1), then the left-most bit of a negative number is always a one. Two's complement addition is the same as the addition of two positive numbers.
One prior multiplier multiplies eight-bits per clock cycle using straight multiplication. Eight carry-save adders are used in that prior multiplier.
In another prior approach, Booth's algorithm is used in generating partial products, and stages of carry-save adders, plus a carry propagate adder at a final stage, is used to obtain a final product.
Multiplication is one of several floating-point operations. A floating-point number includes a mantissa, an exponent, and a sign bit that indicates the sign of the mantissa. For floating-point multiplication, the exponents are added and the mantissas are multiplied. The result is then normalized.
FIG. 2 illustrates examples of floating-point numbers. Single precision floating-point 10 includes a sign bit 25, an 8-bit exponent portion 23, and a 23-bit mantissa portion 21. Double precision floating-point number 12 includes a sign bit 31, an 11-bit exponent portion 29, and a 52-bit mantissa portion 27. Extended precision floating-point 14 includes a sign bit 39, a 15-bit exponent portion 37, a J-bit 35, and a 63-bit mantissa 33. The J-bit corresponds to the bit to the left of the decimal point in a floating-point number.
As seen above, the floating-point formats yield relatively long mantissas to be multiplied. Therefore, for a digital computer using the floating-point formats, the performance of the computer's multiplication circuitry becomes a key factor in the computer's overall floating-point performance.